Digital maps are found in a wide variety of devices, including car navigation systems, hand-held GPS units, mobile phones, and in many websites such as GOOGLE MAPS and MAPQUEST. Although digital maps are easy to use from an end-user's perspective, creating a digital map is a difficult and time-consuming process. Every digital map begins with a set of raw data corresponding to millions of streets and intersections. The raw map data is derived from a variety of sources, each source providing different amounts and types of information. In many cases, data from different sources is inaccurate and out of date. Oftentimes the data from the different sources are in a format that is not suitable for use in a real map. Integrating data from these heterogeneous sources so that it can be used and displayed properly is an enormous challenge.
In particular, physical roads in the real world are represented in the raw data as a series of connected road segments. The data representation of each road segment includes a set of attributes, such as the street name, speed information, or the paved status of the segment. Some segments of a road may have missing or incomplete attribute data. To ensure consistency and completeness of the map data, it is important to be able to associate the same attribute with all the segments of a particular road or series of roads. However, using conventional map editors to edit such attributes is difficult because a single road can consist of many connected segments, each of which must be identified before its attributes can be modified.
One conventional technique for editing attributes involves selecting one road segment at a time. Thus, in order to apply the same attribute to a series of connected road segments, the user must individually select each road segment that needs to be edited. However, selecting road segments in this manner is extremely time consuming, especially if the user needs to apply the same set of attributes to a long road that has of hundreds of segments.
Another conventional technique for adding attributes involves selecting a group of road segments that are located within a certain area of a displayed map. This can be done, for example, by using the mouse to draw a box around an area of the map. However, this technique of selecting road segments is over-inclusive and results in too many road segments being selected. For example, the user may need to select a series of 30 connected segments that run diagonally through a particular area of a map that contains 900 road segments. By selecting all the segments within that area, the user is selecting not only the road segments with attributes that need to be modified, but also many other road segments with attributes that should not be modified.